package 链表;

public class LC_142环形链表II {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args){
        ListNode head=new ListNode(3);
        head.next=new ListNode(2);
        head.next.next=new ListNode(0);
        head.next.next.next=new ListNode(-4);
        int pos=1;
        ListNode listnode=detectCycle(head);
        ListNode cur=listnode;
        while(cur!=null){
            System.out.print(cur.val+" ");
        }
    }
    public static ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;//快指针移动两格
            slow=slow.next;//慢指针 一格
            if(slow==fast){//相遇代表有环
                ListNode index1=fast;
                ListNode index2=head;
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
